package warm100;

import java.util.ArrayList;
import java.util.List;

public class partitionLabels_763 {
    public List<Integer> partitionLabels(String s) {
        //划分为尽可能多的片段，开始毫无思路
        //题解思路，从左向右合并区间，所以保存每个字母最后出现的下标，所有下标合成的区间必须是同一个片段
        //同理，区间内的所有字母重复该过程，扩充该区间右边界
        //遍历 s，由于当前区间必须包含所有 s[i]，所以用 last[s[i]] 更新区间右端点 end 的最大值
        char[]chars=s.toCharArray();
        List<Integer> ans = new ArrayList<>();
        int end=0, start=0;
        int[]last=new int[26];  //最后出现的下标位置，用来扩充当前处理的区间右边界
        for(int i=0;i<chars.length;i++)
            last[ s.charAt(i) - 'a'] = i ;
        for(int i=0;i<chars.length;i++){
            end=Math.max(last[chars[i] - 'a' ] , end );       //更新最右边界
            if(end==i){
                ans.add(end-start+1);      //end==i  说明该区间所有边界扩张完毕
                start=i+1;
            }
        }
        return ans;
    }
}
